A database is a collection of logically related data that is accessible by one or more users. A popular type of database system is the relational database management system, which includes relational tables made up of rows and columns. Each row represents an occurrence of an entity defined by the table, with an entity being a person, place, or thing about which the table contains information.
To extract data from a relational table, queries according to a standard database query language (e.g. Structured Query Language or SQL) can be used. Examples of SQL statements include INSERT, SELECT, UPDATE, and DELETE. The SELECT statement is used to retrieve information from the database and to organize information for presentation to the user or to an application program. The SELECT statement can also specify a join operation to join rows of multiple tables. A common type of join operation is a simple join (or equijoin), which uses an equal (=) comparison operator to join rows from multiple tables. Another type of join is a non-equijoin, or inequality join, which is based on operators other than the equal comparison (e.g., >, <, ≧, ≦, etc.).
Conventionally, join algorithms have been implemented to enable efficient performance of equijoins. However, if no equality terms are present in a join predicate of a query, an inequality join is specified and then a product join is typically performed. In a product join, every left relation row is compared with every right relation row. The terms “left relation” and “right relation” refer to the relations on the left and right sides, respectively, of an inequality operator (e.g., <, >, ≦, ≧). Efficient algorithms have typically not been provided for inequality joins.